1. Field of the Invention
The present invention relates to a root finding method and a root finding circuit of a one-element quadratic polynomial over a finite field used for elliptic cryptosystem and the like.
2. Description of Related Art
Prior to describing a conventional technique, computation of a finite field will first be described.
(Computation of Finite Field),
A finite field GF(2m) is a set formed of 2m elements, and each element is represented using vector representation. An element of the degree 2mxe2x88x921 is referred to as primitive root. According to the vector representation, GF(2m) is regarded as an m dimensional vector space of GF(2), and an arbitrary element xe2x80x9caxe2x80x9d is represented by an m dimensional numerical vector (a0, a1. . . , amxe2x88x921), where each component ai of the vector is an element over GF(2), i.e., 0 or 1. In vector representation, a vector space is not limited to one type of basis, and representation of an element can vary depending on the basis used.
As for the basis, there are a normal basis and a polynomial basis. The normal basis uses a basis as shown below.
(xcex1, xcex12, xcex122, . . . , xcex12mxe2x88x921)
where the primitive root xcex1 is used so that the followings are linearly independent.
xcex1, xcex12, xcex122, . . . , xcex12mxe2x88x921
The polynomial basis is a basis (1, z, z2, . . . zmxe2x88x921) which is generated from a monic irreducible polynomial of degree m xe2x80x9cfxe2x80x9d over GF(2) serving as a generation polynomial using an element xe2x80x9czxe2x80x9d which is the root of xe2x80x9cfxe2x80x9d. Here, a=(a0, a1, . . . , amxe2x88x921) is regarded as an element over GF(2) [x] where x is a variable, and xe2x80x9caxe2x80x9d is represented by a=amxe2x88x921xmxe2x88x921+. . . +a1x +a0. This representation is referred to as polynomial representation.
Addition of two elements xe2x80x9caxe2x80x9d and xe2x80x9cbxe2x80x9d over GF(2m) is represented by a+b=(a0+b0, a1+b1, . . . , amxe2x88x921+bmxe2x88x921). That is, the two elements may be added over GF(2) for each component. The addition over GF(2) is carried out as Exclusive OR. As for the multiplication of two elements xe2x80x9caxe2x80x9d and xe2x80x9cbxe2x80x9d over GF(2m), methods each employing a normal basis are described in U.S. Pat. No. 4,587,627, xe2x80x9cComputational Method and Apparatus for Finite Field Arithmeticxe2x80x9d and U.S. Pat. No. 4,745, 568, xe2x80x9cComputational Method and Apparatus for Finite Field Multiplication.xe2x80x9d Each of these methods has a drawback that a circuit for implementation is complicated and the circuit scale becomes very large when m is large. The multiplication using a normal basis is described in detail in A. J. Menezes, Ed, xe2x80x9cApplications of Finite Fieldsxe2x80x9d, Kluwer Academic Pub. On the other hand, the method using a polynomial basis is described in detail in J. Weldolon, Jr., xe2x80x9cError-Correcting Codesxe2x80x9d, MIT Press. As compared with the multiplication using a normal basis, the method using the polynomial basis has an advantage that the circuit is simple, the circuit scale does not become so large even when m is large, and high speed operation with a high rate clock is possible.
(Elliptic Cryptosystem)
The elliptic cryptosystem is a cryptosystem using addition of GF(2m) rational points of an elliptic curve
E:y2+xy=x3+c1x2+c2, c1xcex5GF(2m)
over GF(2m). In this cryptosystem, a message is mapped onto a rational point over an elliptic curve E to form an encrypted sentence at the time of encryption. At the time of decryption, the encrypted sentence is mapped onto a rational point over an elliptic curve E to restore the original message.
In this elliptic cryptosystem, the encrypted sentence is formed of a rational point (xc, yc) on the elliptic curve E. A message having m bits becomes 2m bits when encrypted. This results in a drawback that the size of the encrypted sentence becomes twice as compared with other cryptosystems using an information group over a finite field. For eliminating this drawback, there is such a method as to make the encrypted sentence have a size which is equal to one bit plus the size obtained when other cryptosystems using an information group over a finite field are employed. For implementing this, it is necessary to find roots of a quadratic polynomial over GF(2m).
(Mapping from Message onto Rational Point)
For mapping a message onto a rational point, typically the message is subjected to binary expansion, and blocking every mxe2x80x2 bits, where mxe2x80x2 less than m. This message is used as components of mxe2x80x2 high-order bits of an element M of GF(2m) represented as a vector, and components of m-mxe2x80x2 low-order bits are filled up with a random number. This element M is associated with an x coordinate of the elliptic curve E. A rational point having an x coordinate equivalent to the element M is calculated. In other words, y satisfying the relation
y2+My=M3+c1M2+c2
is found. If y does not exist, then the m-mxe2x80x2 low-order bits are filled up with a different random number, and y is found again. If y exists and y is found to be Y, the map of the message onto a rational point is defined to be (M, Y).
If at this time the elliptic curve E is converted in variable by z=y/x, then z satisfying the relation
z2+z=a
where   a  =      M    +          c      1        +                  c        2                    M        2            
is found. From this z, Y=Mz is found. Mapping from the message to the point has thus been conducted.
(Reduction of Encrypted Sentence)
Since the elliptic curve E can be represented by a quadratic polynomial as described above, there are only two rational points on the elliptic curve E each of which has an element X over GF(2m) as the value of its x coordinate. Therefore, a cryptosystem sentence (X, Y) can be represented by X and 1-bit information. If z=Y/X is found and its lowest order bit z0 is used as the cryptograph sentence together with X, therefore, then the cryptograph sentence is reduced by mxe2x88x921 bits. In the case where this method is used, Y corresponding to X can be found by letting the least significant bit be z0 and solving z2+z=a and ,   a  =      X    +          c      1        +                  c        2                    X        2            
and letting Y=Xz at the time of decryption. The cryptograph sentence (X, Y) can be thus reconstructed. The configuration of the elliptic cryptosystem is described in detail in A. J. Menezes, xe2x80x9cElliptic Curve Public Key Cryptosystemsxe2x80x9d, Kluwer Academic Pub.
As for the root finding method of the quadratic polynomial, a method of the case where a normal basis is used is generally known. As described above, however, multiplication using a normal basis involves a complicated circuit. In addition, a root finding method, and root finding apparatus of the quadratic polynomial has not been known to the person in the art.
The present invention has been conceived to solve the above described problem. An object of the present invention is to provide a root finding method, and root finding apparatus, of a quadratic polynomial over a finite field using a polynomial basis capable of operating at high speed and making the circuit scale in implementation small.
The above described object is achieved by the following aspects of the present invention.
In accordance with a first aspect of the present invention, assuming that an expansion degree m is selected so that a polynomial f=xm+xmxe2x88x921+. . . x+1 over GF(2) is irreducible and the polynomial f is used as a generation polynomial of GF (2m), a root finding circuit of a quadratic polynomial includes mxe2x88x923 cascade-connected exclusive OR gates X(1, 0) to X(1, mxe2x88x924) each supplied with a corresponding bit of the element xe2x80x9caxe2x80x9d at a first input thereof and each supplied with output of an exclusive OR gate of an immediately preceding stage at a second input, a second input of only X(1, 0) being supplied with amxe2x88x921instead of the output of an exclusive OR gate of an immediately preceding stage, and m/2xe2x88x921 exclusive OR gates X(2, 0) to X(2, m/2xe2x88x922) respectively supplied with amxe2x88x921 and outputs of X(1, 1), X(1, 3), . . . , X(1, mxe2x88x925) at first inputs and each supplied with a0 at a second input thereof, in which outputs of the exclusive OR gates X(2, 0) to X(2, m/2xe2x88x922), and outputs of the exclusive OR gates X(1, 0), X(1, 2), . . . , X(1, mxe2x88x924), and the a0 are output as a root z=(z0, z1, . . . , zmxe2x88x921) of z2+z+a.
In accordance with a second aspect of the present invention, a root finding circuit of a quadratic polynomial includes an exclusive OR gate X(1, mxe2x88x923) supplied with a corresponding bit of the element xe2x80x9caxe2x80x9d and the output of X(1, mxe2x88x924) at inputs thereof, and output of the exclusive OR gate X(1, mxe2x88x923) is output together with outputs of the other exclusive OR gates.
In accordance with a third aspect of the present invention, a root finding circuit of a quadratic polynomial includes mxe2x88x923 cascade-connected exclusive OR gates X(1, 0) to X(1, mxe2x88x924) each supplied with a corresponding bit of the element xe2x80x9caxe2x80x9d at a first input thereof and each supplied with output of an exclusive OR gate of an immediately preceding stage at a second input, a second input of only X(1, 0) being supplied with am/2 instead of the output of an exclusive OR gate of an immediately preceding stage, and m/2xe2x88x921 exclusive OR gates X(2, 0) to X(2, m/2xe2x88x922) respectively supplied with outputs of X(1, 0), X(1, 2), . . . , X(1, mxe2x88x924) at first inputs and each supplied with a0 at a second input thereof, and outputs of the exclusive OR gates X(2, 0) to X(2, m/2xe2x88x922), outputs of the exclusive OR gates X(1, 1), X(1, 3), . . . , X(1, mxe2x88x925), am/2, and a0 are output as a root z=(z0, z1, . . . , zmxe2x88x921) of z2+z+a.
In accordance with a fourth aspect of the present invention, a root finding circuit of a quadratic polynomial over includes an exclusive OR gate X(1, mxe2x88x923) supplied with a corresponding bit of the element xe2x80x9caxe2x80x9d and the output of X(1, mxe2x88x924) at inputs thereof, and output of the exclusive OR gate X(1, mxe2x88x923) is output together with outputs of the other exclusive OR gates.
In accordance with a fifth aspect of the present invention, a root finding circuit of a quadratic polynomial includes a first circuit for finding n outputs z (where n less than mxe2x88x921) by using exclusive OR gates of a predetermined number of stages beginning from a first stage of the circuit according to the first aspect, and a second circuit for finding such mxe2x88x921n outputs z that those outputs and the output z of the first circuit will not duplicate, by using exclusive OR gates of a predetermined number of stages beginning from a first stage of the circuit according to the second aspect, the second circuit is connected to the first circuit, and all of the roots z=(z0, z1, . . . , zmxe2x88x921) of z2+z+a are found.
In accordance with a sixth aspect of the present invention, a root finding circuit of a quadratic polynomial includes an exclusive OR gate supplied with output of a final stage of the cascade-connected exclusive OR gates in the first circuit at a first input thereof and supplied with output of a final stage of the cascade-connected exclusive OR gates in the second circuit at a second input thereof, and an output of the exclusive OR gate is output together with outputs of the other exclusive OR gates.
In accordance with a seventh aspect of the present invention, assuming that a polynomial f=xm+xmxe2x88x921+. . . x+1 over GF(2) is irreducible and has an expansion degree m and the f is used as a generation polynomial of GF(2m), a root finding method of a quadratic polynomial includes the steps of deriving an exclusive OR of mutually corresponding bits of the element xe2x80x9caxe2x80x9d, letting the derived exclusive OR value be a value of a corresponding bit of z, thereafter letting a value of an exclusive OR between a corresponding bit of the element xe2x80x9caxe2x80x9d and immediately derived bit of z be a value of next corresponding bit of z, and thereafter repeating these steps and thereby find z.